package cn.bouncyslime.algorithms.sort.insertSort;
/*
 * 希尔排序，又称缩小增量排序，也是属于插入排序的方法，但是在效率上有所改进
 * 先将整个待排序记录序列分割为若干个子序列，对子序列分别进行插入排序
 * 使整个序列中的记录基本有序时，再对全体进行一次插入排序
 * */
public class ShellSort {
	public void shellSort(int[] array) {
		int length = array.length;
		int flag=0,flag2=0;		// 用来记录比较次数和移动次数
		
		System.out.println("排序之前：");
		printArray(array);
		System.out.println("排序过程中：");
		
		// 此for循环用于改变取数的间隔，取数间隔不断缩小，最后为1，此时就相当于将数组进行直接插入排序
		for(int interval=length/2; interval>0; interval/=2) {
			System.out.println("选取的间隔"+interval);
			// 在一定的取数间隔下，遍历拆分成的interval个子数组
			for(int m=0; m<interval; m++) {
				// 将每一个拆分的子数组中的数进行插入排序
				for(int i=m; i<length-interval; i+=interval) {
					for(int j=m; j<=i; j+=interval) {
						if(array[i+interval] < array[j]) {
							int temp = array[j];
							array[j] = array[i+interval];
							array[i+interval] = temp;
							flag2 ++;
						}
						flag ++;
					}
				}
				printArray(array);
			}
		}
		
		System.out.println("最终输出结果为：");
		System.out.println("进行了"+flag+"次比较！");
		System.out.println("进行了"+flag2+"次移动！");
		printArray(array);
	}
	
	public void printArray(int[] array) {
		for(int i=0; i<array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		ShellSort ss = new ShellSort();
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		ss.shellSort(array);
	}
}